package com.cn.algorithm02.class02;

import com.cn.algorithm02.class01.CodeUtil;

import java.util.Arrays;

/**
 * 插入排序： 顺序排列：光标的数字和前一个数字比较，小的往前，光标减一，
 * 接着和前一个比较，最终将最小值替换到最左边
 * 时间复杂度计算：
 * 原数据为顺序时， 每次只用只比较一次，所以时间复杂度为O1
 * 原数据为你顺序时，每次都要从右两两比较到最左边On，n个数字所以最后为O(n^2)
 *
 * 空间复杂度计算：输入参数和输出跟结果相关的空间不计入时间复杂度，只有用于辅助的新对象计入空间复杂度
 */
public class C03_InsertSort {
    public static void main(String[] args) {
        int num = 10000;
        int maxValue = 100;
        int maxSize = 100;
        boolean b = false;

        for (int i = 0; i < num; i++) {
            int[] arr = CodeUtil.generatorArray(maxValue, maxSize, false);
            System.out.println(i + " " + arr.length);
            if (arr == null || arr.length < 2) {return;}
            int[] arr1 = CodeUtil.copyArr(arr);
            int[] arr2 = CodeUtil.copyArr(arr);

            insertSort(arr1);
            compTest(arr2);
            b = CodeUtil.compareArr(arr1, arr2);
        }

        System.out.println("sort result: " + b);
    }

    // 对数器
    public static void compTest(int[] arr) {
        Arrays.sort(arr);
    }

    // i = 0 不用比较，跳过
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j+1] ; j--) {
                CodeUtil.swap(arr, j, j+1);
            }
        }
    }

}
